#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int StackDataType;

typedef struct Stack
{
	int size;
	int capacity;
	StackDataType* data;
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->data = (StackDataType*)malloc(sizeof(StackDataType) * 4);
	if (ps->data == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = 4;
}

void StackPush(Stack* ps, StackDataType x)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		StackDataType* tmp = (StackDataType*)realloc(ps->data, sizeof(StackDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->data = tmp;
		ps->capacity *= 2;
	}
	ps->data[ps->size] = x;
	ps->size++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

StackDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->size);
	return ps->data[ps->size - 1];

}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->size == NULL;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int partsort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev < cur)
			Swap(&a[prev], &a[cur]);
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a,int left,int right)
{
	Stack s;
	StackInit(&s);
	StackPush(&s, left);
	StackPush(&s, right);
	while (!StackEmpty(&s))
	{
		int end = StackTop(&s);
		StackPop(&s);
		int begin = StackTop(&s);
		StackPop(&s);
		int keyi = partsort(a, begin, end);
		if (begin < keyi - 1)
		{
			StackPush(&s, begin);
			StackPush(&s, keyi-1);
		}
		if (keyi + 1 < end)
		{
			StackPush(&s, keyi+1);
			StackPush(&s, end);
		}
	}
}




int main()
{
	int a[] = { 6,5,1,23,4,5,-1,-5 };
	int len = sizeof(a) / sizeof(int);
	QuickSort(a, 0, len - 1);
	int i = 0;
	for (i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return;
}